home *** CD-ROM | disk | FTP | other *** search
/ SGI Developer Toolbox 6.1 / SGI Developer Toolbox 6.1 - Disc 4.iso / public / fax / src / libtiff / tif_fax3.c < prev    next >
C/C++ Source or Header  |  1994-08-01  |  29KB  |  1,094 lines
  1. #ifndef lint
  2. static char rcsid[] = "$Header: /usr/people/sam/fax/libtiff/RCS/tif_fax3.c,v 1.74 1994/04/06 22:28:16 sam Exp $";
  3. #endif
  4.  
  5. /*
  6.  * Copyright (c) 1990, 1991, 1992 Sam Leffler
  7.  * Copyright (c) 1991, 1992 Silicon Graphics, Inc.
  8.  *
  9.  * Permission to use, copy, modify, distribute, and sell this software and 
  10.  * its documentation for any purpose is hereby granted without fee, provided
  11.  * that (i) the above copyright notices and this permission notice appear in
  12.  * all copies of the software and related documentation, and (ii) the names of
  13.  * Sam Leffler and Silicon Graphics may not be used in any advertising or
  14.  * publicity relating to the software without the specific, prior written
  15.  * permission of Sam Leffler and Silicon Graphics.
  16.  * 
  17.  * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, 
  18.  * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY 
  19.  * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.  
  20.  * 
  21.  * IN NO EVENT SHALL SAM LEFFLER OR SILICON GRAPHICS BE LIABLE FOR
  22.  * ANY SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND,
  23.  * OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  24.  * WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF 
  25.  * LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE 
  26.  * OF THIS SOFTWARE.
  27.  */
  28.  
  29. /*
  30.  * TIFF Library.
  31.  *
  32.  * CCITT Group 3 and Group 4 Compression Support.
  33.  */
  34. #include "tiffiop.h"
  35. #include "tif_fax3.h"
  36. #define    G3CODES
  37. #include "t4.h"
  38. #define    G3STATES
  39. #include "g3states.h"
  40. #include <assert.h>
  41. #include <stdio.h>
  42.  
  43. typedef struct {
  44.     Fax3BaseState b;
  45. } Fax3DecodeState;
  46.  
  47. typedef struct {
  48.     Fax3BaseState b;
  49.     const u_char *wruns;
  50.     const u_char *bruns;
  51.     short    k;            /* #rows left that can be 2d encoded */
  52.     short    maxk;            /* max #rows that can be 2d encoded */
  53. } Fax3EncodeState;
  54.  
  55. #if USE_PROTOTYPES
  56. static    int Fax3Decode1DRow(TIFF*, u_char *, int);
  57. static    int Fax3Encode1DRow(TIFF *, u_char *, int);
  58. static    int findspan(u_char **, int, int, const u_char *);
  59. static    int finddiff(u_char *, int, int, int);
  60. #else
  61. static    int Fax3Encode1DRow();
  62. static    int Fax3Decode1DRow();
  63. static    int findspan();
  64. static    int finddiff();
  65. #endif
  66.  
  67. void
  68. TIFFModeCCITTFax3(tif, isClassF)
  69.     TIFF *tif;
  70.     int isClassF;
  71. {
  72.     if (isClassF)
  73.         tif->tif_options |= FAX3_CLASSF;
  74.     else
  75.         tif->tif_options &= ~FAX3_CLASSF;
  76. }
  77.  
  78. static u_char bitMask[8] =
  79.     { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
  80. #define    isBitSet(sp)    ((sp)->b.data & bitMask[(sp)->b.bit])
  81.  
  82. #define    is2DEncoding(tif) \
  83.     (tif->tif_dir.td_group3options & GROUP3OPT_2DENCODING)
  84. #define    fetchByte(tif, sp) \
  85.     ((tif)->tif_rawcc--, (sp)->b.bitmap[*(u_char *)(tif)->tif_rawcp++])
  86.  
  87. #define    BITCASE(b)            \
  88.     case b:                \
  89.     code <<= 1;            \
  90.     if (data & (1<<(7-b))) code |= 1;\
  91.     len++;                \
  92.     if (code > 0) { bit = b+1; break; }
  93.  
  94. /*
  95.  * Skip over input until an EOL code is found.  The
  96.  * value of len is passed as 0 except during error
  97.  * recovery when decoding 2D data.  Note also that
  98.  * we don't use the optimized state tables to locate
  99.  * an EOL because we can't assume much of anything
  100.  * about our state (e.g. bit position).
  101.  */
  102. static void
  103. DECLARE2(skiptoeol, TIFF*, tif, int, len)
  104. {
  105.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  106.     register int bit = sp->b.bit;
  107.     register int data = sp->b.data;
  108.     int code = 0;
  109.  
  110.     /*
  111.      * Our handling of ``bit'' is painful because
  112.      * the rest of the code does not maintain it as
  113.      * exactly the bit offset in the current data
  114.      * byte (bit == 0 means refill the data byte).
  115.      * Thus we have to be careful on entry and
  116.      * exit to insure that we maintain a value that's
  117.      * understandable elsewhere in the decoding logic.
  118.      */
  119.     if (bit == 0)            /* force refill */
  120.         bit = 8;
  121.     for (;;) {
  122.         switch (bit) {
  123.     again:    BITCASE(0);
  124.         BITCASE(1);
  125.         BITCASE(2);
  126.         BITCASE(3);
  127.         BITCASE(4);
  128.         BITCASE(5);
  129.         BITCASE(6);
  130.         BITCASE(7);
  131.         default:
  132.             if (tif->tif_rawcc <= 0)
  133.                 return;
  134.             data = fetchByte(tif, sp);
  135.             goto again;
  136.         }
  137.         if (len >= 12 && code == EOL)
  138.             break;
  139.         code = len = 0;
  140.     }
  141.     sp->b.bit = bit > 7 ? 0 : bit;    /* force refill */
  142.     sp->b.data = data;
  143. }
  144.  
  145. /*
  146.  * Return the next bit in the input stream.  This is
  147.  * used to extract 2D tag values and the color tag
  148.  * at the end of a terminating uncompressed data code.
  149.  */
  150. static int
  151. DECLARE1(nextbit, TIFF*, tif)
  152. {
  153.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  154.     int bit;
  155.  
  156.     if (sp->b.bit == 0 && tif->tif_rawcc > 0)
  157.         sp->b.data = fetchByte(tif, sp);
  158.     bit = isBitSet(sp);
  159.     if (++(sp->b.bit) > 7)
  160.         sp->b.bit = 0;
  161.     return (bit);
  162. }
  163.  
  164. static void
  165. DECLARE3(bset, register u_char*, cp, register int, n, register int, v)
  166. {
  167.     while (n-- > 0)
  168.         *cp++ = v;
  169. }
  170.  
  171. /*
  172.  * Setup G3-related compression/decompression
  173.  * state before data is processed.  This routine
  174.  * is called once per image -- it sets up different
  175.  * state based on whether or not 2D encoding is used.
  176.  */
  177. static void *
  178. DECLARE2(Fax3SetupState, TIFF*, tif, int, space)
  179. {
  180.     TIFFDirectory *td = &tif->tif_dir;
  181.     Fax3BaseState *sp;
  182.     int cc = space;
  183.     long rowbytes, rowpixels;
  184.  
  185.     if (td->td_bitspersample != 1) {
  186.         TIFFError(tif->tif_name,
  187.             "Bits/sample must be 1 for Group 3/4 encoding/decoding");
  188.         return (0);
  189.     }
  190.     /*
  191.      * Calculate the scanline/tile widths.
  192.      */
  193.     if (isTiled(tif)) {
  194.         rowbytes = TIFFTileRowSize(tif);
  195.         rowpixels = tif->tif_dir.td_tilewidth;
  196.     } else {
  197.         rowbytes = TIFFScanlineSize(tif);
  198.         rowpixels = tif->tif_dir.td_imagewidth;
  199.     }
  200.     if (is2DEncoding(tif) || td->td_compression == COMPRESSION_CCITTFAX4)
  201.         cc += rowbytes+1;
  202.     tif->tif_data = _TIFFmalloc(cc);
  203.     if (tif->tif_data == NULL) {
  204.         TIFFError("Fax3SetupState",
  205.             "%s: No space for Fax3 state block", tif->tif_name);
  206.         return (0);
  207.     }
  208.     sp = (Fax3BaseState *)tif->tif_data;
  209.     sp->rowbytes = rowbytes;
  210.     sp->rowpixels = rowpixels;
  211.     sp->bitmap = TIFFGetBitRevTable(tif->tif_fillorder != td->td_fillorder);
  212.     sp->white = (td->td_photometric == PHOTOMETRIC_MINISBLACK);
  213.     if (is2DEncoding(tif) || td->td_compression == COMPRESSION_CCITTFAX4) {
  214.         /*
  215.          * 2d encoding/decoding requires a scanline
  216.          * buffer for the ``reference line''; the
  217.          * scanline against which delta encoding
  218.          * is referenced.  The reference line must
  219.          * be initialized to be ``white'' (done elsewhere).
  220.          */
  221.         sp->refline = (u_char *)tif->tif_data + space + 1;
  222.         /*
  223.          * Initialize pixel just to the left of the
  224.          * reference line to white.  This extra pixel
  225.          * simplifies the edge-condition logic.
  226.          */
  227.         sp->refline[-1] = sp->white ? 0xff : 0x00;
  228.     } else
  229.         sp->refline = 0;
  230.     return (sp);
  231. }
  232.  
  233. /*
  234.  * Setup state for decoding a strip.
  235.  */
  236. static
  237. DECLARE1(Fax3PreDecode, TIFF*, tif)
  238. {
  239.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  240.  
  241.     if (sp == NULL) {
  242.         sp = (Fax3DecodeState *)Fax3SetupState(tif, sizeof (*sp));
  243.         if (!sp)
  244.             return (0);
  245.     }
  246.     sp->b.bit = 0;            /* force initial read */
  247.     sp->b.data = 0;
  248.     sp->b.tag = G3_1D;
  249.     if (sp->b.refline)
  250.         bset(sp->b.refline, sp->b.rowbytes, sp->b.white ? 0xff : 0x00);
  251.     /*
  252.      * If image has EOL codes, they precede each line
  253.      * of data.  We skip over the first one here so that
  254.      * when we decode rows, we can use an EOL to signal
  255.      * that less than the expected number of pixels are
  256.      * present for the scanline.
  257.      */
  258.     if ((tif->tif_options & FAX3_NOEOL) == 0) {
  259.         skiptoeol(tif, 0);
  260.         if (is2DEncoding(tif))
  261.             /* tag should always be 1D! */
  262.             sp->b.tag = nextbit(tif) ? G3_1D : G3_2D;
  263.     }
  264.     return (1);
  265. }
  266.  
  267. /*
  268.  * Fill a span with ones.
  269.  */
  270. static void
  271. DECLARE3(fillspan, register char*, cp, register int, x, register int, count)
  272. {
  273.     static const unsigned char masks[] =
  274.         { 0, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff };
  275.  
  276.     if (count <= 0)
  277.         return;
  278.     cp += x>>3;
  279.     if (x &= 7) {            /* align to byte boundary */
  280.         if (count < 8 - x) {
  281.             *cp++ |= masks[count] >> x;
  282.             return;
  283.         }
  284.         *cp++ |= 0xff >> x;
  285.         count -= 8 - x;
  286.     }
  287.     while (count >= 8) {
  288.         *cp++ = 0xff;
  289.         count -= 8;
  290.     }
  291.     *cp |= masks[count];
  292. }
  293.  
  294. /*
  295.  * Decode the requested amount of data.
  296.  */
  297. static
  298. DECLARE4(Fax3Decode, TIFF*, tif, u_char*, buf, u_long, occ, u_int, s)
  299. {
  300.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  301.     int status;
  302.  
  303.     memset(buf, 0, occ);        /* decoding only sets non-zero bits */
  304.     while ((long)occ > 0) {
  305.         if (sp->b.tag == G3_1D)
  306.             status = Fax3Decode1DRow(tif, buf, sp->b.rowpixels);
  307.         else
  308.             status = Fax3Decode2DRow(tif, buf, sp->b.rowpixels);
  309.         /*
  310.          * For premature EOF, stop decoding and return
  311.          * the buffer with the remainder white-filled.
  312.          */
  313.         if (status == G3CODE_EOF)
  314.             return (status);
  315.         if (is2DEncoding(tif)) {
  316.             /*
  317.              * Fetch the tag bit that indicates
  318.              * whether the next row is 1d or 2d
  319.              * encoded.  If 2d-encoded, then setup
  320.              * the reference line from the decoded
  321.              * scanline just completed.
  322.              */
  323.             sp->b.tag = nextbit(tif) ? G3_1D : G3_2D;
  324.             if (sp->b.tag == G3_2D)
  325.                 memcpy(sp->b.refline, buf, sp->b.rowbytes);
  326.         }
  327.         buf += sp->b.rowbytes;
  328.         occ -= sp->b.rowbytes;
  329.         if (occ > 0)
  330.             tif->tif_row++;
  331.     }
  332.     return (1);
  333. }
  334.  
  335. /*
  336.  * Decode a run of white.
  337.  */
  338. static int
  339. DECLARE1(decode_white_run, TIFF*, tif)
  340. {
  341.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  342.     short state = sp->b.bit;
  343.     short action;
  344.     int runlen = 0;
  345.  
  346.     for (;;) {
  347.         if (sp->b.bit == 0) {
  348.     nextbyte:
  349.             if (tif->tif_rawcc <= 0)
  350.                 return (G3CODE_EOF);
  351.             sp->b.data = fetchByte(tif, sp);
  352.         }
  353.         action = TIFFFax1DAction[state][sp->b.data];
  354.         state = TIFFFax1DNextState[state][sp->b.data];
  355.         if (action == ACT_INCOMP)
  356.             goto nextbyte;
  357.         if (action == ACT_INVALID)
  358.             return (G3CODE_INVALID);
  359.         if (action == ACT_EOL)
  360.             return (G3CODE_EOL);
  361.         sp->b.bit = state;
  362.         action = RUNLENGTH(action - ACT_WRUNT);
  363.         runlen += action;
  364.         if (action < 64)
  365.             return (runlen);
  366.     }
  367.     /*NOTREACHED*/
  368. }
  369.  
  370. /*
  371.  * Decode a run of black.
  372.  */
  373. static int
  374. DECLARE1(decode_black_run, TIFF*, tif)
  375. {
  376.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  377.     short state = sp->b.bit + 8;
  378.     short action;
  379.     int runlen = 0;
  380.  
  381.     for (;;) {
  382.         if (sp->b.bit == 0) {
  383.     nextbyte:
  384.             if (tif->tif_rawcc <= 0)
  385.                 return (G3CODE_EOF);
  386.             sp->b.data = fetchByte(tif, sp);
  387.         }
  388.         action = TIFFFax1DAction[state][sp->b.data];
  389.         state = TIFFFax1DNextState[state][sp->b.data];
  390.         if (action == ACT_INCOMP)
  391.             goto nextbyte;
  392.         if (action == ACT_INVALID)
  393.             return (G3CODE_INVALID);
  394.         if (action == ACT_EOL)
  395.             return (G3CODE_EOL);
  396.         sp->b.bit = state;
  397.         action = RUNLENGTH(action - ACT_BRUNT);
  398.         runlen += action;
  399.         if (action < 64)
  400.             return (runlen);
  401.         state += 8;
  402.     }
  403.     /*NOTREACHED*/
  404. }
  405.  
  406. /*
  407.  * Process one row of 1d Huffman-encoded data.
  408.  */
  409. static int
  410. DECLARE3(Fax3Decode1DRow, TIFF*, tif, u_char*, buf, int, npels)
  411. {
  412.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  413.     int x = 0;
  414.     int runlen;
  415.     short action;
  416.     short color = sp->b.white;
  417.     static const char module[] = "Fax3Decode1D";
  418.  
  419.     for (;;) {
  420.         if (color == sp->b.white)
  421.             runlen = decode_white_run(tif);
  422.         else
  423.             runlen = decode_black_run(tif);
  424.         switch (runlen) {
  425.         case G3CODE_EOF:
  426.             TIFFWarning(module,
  427.                 "%s: Premature EOF at scanline %d (x %d)",
  428.                 tif->tif_name, tif->tif_row, x);
  429.             return (G3CODE_EOF);
  430.         case G3CODE_INVALID:    /* invalid code */
  431.             /*
  432.              * An invalid code was encountered.
  433.              * Flush the remainder of the line
  434.              * and allow the caller to decide whether
  435.              * or not to continue.  Note that this
  436.              * only works if we have a G3 image
  437.              * with EOL markers.
  438.              */
  439.             TIFFError(module,
  440.                "%s: Bad code word at scanline %d (x %d)",
  441.                tif->tif_name, tif->tif_row, x);
  442.             goto done;
  443.         case G3CODE_EOL:    /* premature end-of-line code */
  444.             TIFFWarning(module,
  445.                 "%s: Premature EOL at scanline %d (x %d)",
  446.                 tif->tif_name, tif->tif_row, x);
  447.             return (1);    /* try to resynchronize... */
  448.         }
  449.         if (x+runlen > npels)
  450.             runlen = npels-x;
  451.         if (runlen > 0) {
  452.             if (color)
  453.                 fillspan((char *)buf, x, runlen);
  454.             x += runlen;
  455.             if (x >= npels)
  456.                 break;
  457.         }
  458.         color = !color;
  459.     }
  460. done:
  461.     /*
  462.      * Cleanup at the end of the row.  This convoluted
  463.      * logic is merely so that we can reuse the code with
  464.      * two other related compression algorithms (2 & 32771).
  465.      *
  466.      * Note also that our handling of word alignment assumes
  467.      * that the buffer is at least word aligned.  This is
  468.      * the case for most all versions of malloc (typically
  469.      * the buffer is returned longword aligned).
  470.      */
  471.     if ((tif->tif_options & FAX3_NOEOL) == 0)
  472.         skiptoeol(tif, 0);
  473.     if (tif->tif_options & FAX3_BYTEALIGN)
  474.         sp->b.bit = 0;
  475.     if ((tif->tif_options & FAX3_WORDALIGN) && ((long)tif->tif_rawcp & 1))
  476.         (void) fetchByte(tif, sp);
  477.     return (x == npels ? 1 : G3CODE_EOL);
  478. }
  479.  
  480. /*
  481.  * Group 3 2d Decoding support.
  482.  */
  483.  
  484. /*
  485.  * Return the next uncompressed mode code word.
  486.  */
  487. static int
  488. DECLARE1(decode_uncomp_code, TIFF*, tif)
  489. {
  490.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  491.     short code;
  492.  
  493.     do {
  494.         if (sp->b.bit == 0 || sp->b.bit > 7) {
  495.             if (tif->tif_rawcc <= 0)
  496.                 return (UNCOMP_EOF);
  497.             sp->b.data = fetchByte(tif, sp);
  498.         }
  499.         code = TIFFFaxUncompAction[sp->b.bit][sp->b.data];
  500.         sp->b.bit = TIFFFaxUncompNextState[sp->b.bit][sp->b.data];
  501.     } while (code == ACT_INCOMP);
  502.     return (code);
  503. }
  504.  
  505. /*
  506.  * Process one row of 2d encoded data.
  507.  */
  508. int
  509. DECLARE3(Fax3Decode2DRow, TIFF*, tif, u_char*, buf, int, npels)
  510. {
  511. #define    PIXEL(buf,ix)    ((((buf)[(ix)>>3]) >> (7-((ix)&7))) & 1)
  512.     Fax3DecodeState *sp = (Fax3DecodeState *)tif->tif_data;
  513.     int a0 = -1;
  514.     int b1, b2;
  515.     int run1, run2;        /* for horizontal mode */
  516.     short mode;
  517.     short color = sp->b.white;
  518.     static const char module[] = "Fax3Decode2D";
  519.  
  520.     do {
  521.         if (sp->b.bit == 0 || sp->b.bit > 7) {
  522.             if (tif->tif_rawcc <= 0) {
  523.                 TIFFError(module,
  524.                     "%s: Premature EOF at scanline %d",
  525.                     tif->tif_name, tif->tif_row);
  526.                 return (G3CODE_EOF);
  527.             }
  528.             sp->b.data = fetchByte(tif, sp);
  529.         }
  530.         mode = TIFFFax2DMode[sp->b.bit][sp->b.data];
  531.         sp->b.bit = TIFFFax2DNextState[sp->b.bit][sp->b.data];
  532.         switch (mode) {
  533.         case MODE_NULL:
  534.             break;
  535.         case MODE_PASS:
  536.             b2 = finddiff(sp->b.refline, a0, npels, !color);
  537.             b1 = finddiff(sp->b.refline, b2, npels, color);
  538.             b2 = finddiff(sp->b.refline, b1, npels, !color);
  539.             if (color) {
  540.                 if (a0 < 0)
  541.                     a0 = 0;
  542.                 fillspan((char *)buf, a0, b2 - a0);
  543.             }
  544.             a0 = b2;
  545.             break;
  546.         case MODE_HORIZ:
  547.             if (color == sp->b.white) {
  548.                 run1 = decode_white_run(tif);
  549.                 run2 = decode_black_run(tif);
  550.             } else {
  551.                 run1 = decode_black_run(tif);
  552.                 run2 = decode_white_run(tif);
  553.             }
  554.             if (run1 >= 0 && run2 >= 0) {
  555.                 /*
  556.                  * Do the appropriate fill.  Note that we exit
  557.                  * this logic with the same color that we enter
  558.                  * with since we do 2 fills.  This explains the
  559.                  * somewhat obscure logic below.
  560.                  */
  561.                 if (a0 < 0)
  562.                     a0 = 0;
  563.                 if (a0 + run1 > npels)
  564.                     run1 = npels - a0;
  565.                 if (color)
  566.                     fillspan((char *)buf, a0, run1);
  567.                 a0 += run1;
  568.                 if (a0 + run2 > npels)
  569.                     run2 = npels - a0;
  570.                 if (!color)
  571.                     fillspan((char *)buf, a0, run2);
  572.                 a0 += run2;
  573.             }
  574.             break;
  575.         case MODE_VERT_V0:
  576.         case MODE_VERT_VR1:
  577.         case MODE_VERT_VR2:
  578.         case MODE_VERT_VR3:
  579.         case MODE_VERT_VL1:
  580.         case MODE_VERT_VL2:
  581.         case MODE_VERT_VL3:
  582.             b2 = finddiff(sp->b.refline, a0, npels, !color);
  583.             b1 = finddiff(sp->b.refline, b2, npels, color);
  584.             b1 += mode - MODE_VERT_V0;
  585.             if (color) {
  586.                 if (a0 < 0)
  587.                     a0 = 0;
  588.                 fillspan((char *)buf, a0, b1 - a0);
  589.             }
  590.             color = !color;
  591.             a0 = b1;
  592.             break;
  593.             case MODE_UNCOMP:
  594.             /*
  595.              * Uncompressed mode: select from the
  596.              * special set of code words.
  597.              */
  598.             if (a0 < 0)
  599.                 a0 = 0;
  600.             do {
  601.                 mode = decode_uncomp_code(tif);
  602.                 switch (mode) {
  603.                 case UNCOMP_RUN1:
  604.                 case UNCOMP_RUN2:
  605.                 case UNCOMP_RUN3:
  606.                 case UNCOMP_RUN4:
  607.                 case UNCOMP_RUN5:
  608.                     run1 = mode - UNCOMP_RUN0;
  609.                     fillspan((char *)buf, a0+run1-1, 1);
  610.                     a0 += run1;
  611.                     break;
  612.                 case UNCOMP_RUN6:
  613.                     a0 += 5;
  614.                     break;
  615.                 case UNCOMP_TRUN0:
  616.                 case UNCOMP_TRUN1:
  617.                 case UNCOMP_TRUN2:
  618.                 case UNCOMP_TRUN3:
  619.                 case UNCOMP_TRUN4:
  620.                     run1 = mode - UNCOMP_TRUN0;
  621.                     a0 += run1;
  622.                     color = nextbit(tif) ?
  623.                         !sp->b.white : sp->b.white;
  624.                     break;
  625.                 case UNCOMP_INVALID:
  626.                     TIFFError(module,
  627.                 "%s: Bad uncompressed code word at scanline %d",
  628.                         tif->tif_name, tif->tif_row);
  629.                     goto bad;
  630.                 case UNCOMP_EOF:
  631.                     TIFFError(module,
  632.                         "%s: Premature EOF at scanline %d",
  633.                         tif->tif_name, tif->tif_row);
  634.                     return (G3CODE_EOF);
  635.                 }
  636.             } while (mode < UNCOMP_EXIT);
  637.             break;
  638.             case MODE_ERROR_1:
  639.             if ((tif->tif_options & FAX3_NOEOL) == 0) {
  640.                 TIFFWarning(module,
  641.                     "%s: Premature EOL at scanline %d (x %d)",
  642.                     tif->tif_name, tif->tif_row, a0);
  643.                 skiptoeol(tif, 7);    /* seen 7 0's already */
  644.                 return (1);        /* try to synchronize */
  645.             }
  646.             /* fall thru... */
  647.             case MODE_ERROR:
  648.             TIFFError(module,
  649.                 "%s: Bad 2D code word at scanline %d",
  650.                 tif->tif_name, tif->tif_row);
  651.             goto bad;
  652.             default:
  653.             TIFFError(module,
  654.                 "%s: Panic, bad decoding state at scanline %d",
  655.                 tif->tif_name, tif->tif_row);
  656.             return (0);
  657.         }
  658.     } while (a0 < npels);
  659. bad:
  660.     /*
  661.      * Cleanup at the end of row.  We check for
  662.      * EOL separately so that this code can be
  663.      * reused by the Group 4 decoding routine.
  664.      */
  665.     if ((tif->tif_options & FAX3_NOEOL) == 0)
  666.         skiptoeol(tif, 0);
  667.     return (a0 >= npels ? 1 : G3CODE_EOL);
  668. #undef    PIXEL
  669. }
  670.  
  671. /*
  672.  * CCITT Group 3 FAX Encoding.
  673.  */
  674.  
  675. /*
  676.  * Write a variable-length bit-value to
  677.  * the output stream.  Values are
  678.  * assumed to be at most 16 bits.
  679.  */
  680. void
  681. DECLARE3(Fax3PutBits, TIFF*, tif, u_int, bits, u_int, length)
  682. {
  683.     Fax3BaseState *sp = (Fax3BaseState *)tif->tif_data;
  684.     static const int mask[9] =
  685.         { 0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff };
  686.  
  687.     while (length > sp->bit) {
  688.         sp->data |= bits >> (length - sp->bit);
  689.         length -= sp->bit;
  690.         Fax3FlushBits(tif, sp);
  691.     }
  692.     sp->data |= (bits & mask[length]) << (sp->bit - length);
  693.     sp->bit -= length;
  694.     if (sp->bit == 0)
  695.         Fax3FlushBits(tif, sp);
  696. }
  697.  
  698. /*
  699.  * Write a code to the output stream.
  700.  */
  701. static void
  702. DECLARE2(putcode, TIFF*, tif, const tableentry*, te)
  703. {
  704.     Fax3PutBits(tif, te->code, te->length);
  705. }
  706.  
  707. /*
  708.  * Write the sequence of codes that describes
  709.  * the specified span of zero's or one's.  The
  710.  * appropriate table that holds the make-up and
  711.  * terminating codes is supplied.
  712.  */
  713. static void
  714. DECLARE3(putspan, TIFF*, tif, int, span, const tableentry*, tab)
  715. {
  716.     while (span >= 2624) {
  717.         const tableentry *te = &tab[63 + (2560>>6)];
  718.         putcode(tif, te);
  719.         span -= te->runlen;
  720.     }
  721.     if (span >= 64) {
  722.         const tableentry *te = &tab[63 + (span>>6)];
  723.         assert(te->runlen == 64*(span>>6));
  724.         putcode(tif, te);
  725.         span -= te->runlen;
  726.     }
  727.     putcode(tif, &tab[span]);
  728. }
  729.  
  730. /*
  731.  * Write an EOL code to the output stream.  The zero-fill
  732.  * logic for byte-aligning encoded scanlines is handled
  733.  * here.  We also handle writing the tag bit for the next
  734.  * scanline when doing 2d encoding.
  735.  */
  736. void
  737. DECLARE1(Fax3PutEOL, TIFF*, tif)
  738. {
  739.     Fax3BaseState *sp = (Fax3BaseState *)tif->tif_data;
  740.  
  741.     if (tif->tif_dir.td_group3options & GROUP3OPT_FILLBITS) {
  742.         /*
  743.          * Force bit alignment so EOL will terminate on
  744.          * a byte boundary.  That is, force the bit alignment
  745.          * to 16-12 = 4 before putting out the EOL code.
  746.          */
  747.         int align = 8 - 4;
  748.         if (align != sp->bit) {
  749.             if (align > sp->bit)
  750.                 align = sp->bit + (8 - align);
  751.             else
  752.                 align = sp->bit - align;
  753.             Fax3PutBits(tif, 0, align);
  754.         }
  755.     }
  756.     Fax3PutBits(tif, EOL, 12);
  757.     if (is2DEncoding(tif))
  758.         Fax3PutBits(tif, sp->tag == G3_1D, 1);
  759. }
  760.  
  761. static const u_char zeroruns[256] = {
  762.     8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,    /* 0x00 - 0x0f */
  763.     3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,    /* 0x10 - 0x1f */
  764.     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,    /* 0x20 - 0x2f */
  765.     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,    /* 0x30 - 0x3f */
  766.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x40 - 0x4f */
  767.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x50 - 0x5f */
  768.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x60 - 0x6f */
  769.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x70 - 0x7f */
  770.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x80 - 0x8f */
  771.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x90 - 0x9f */
  772.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xa0 - 0xaf */
  773.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xb0 - 0xbf */
  774.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xc0 - 0xcf */
  775.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xd0 - 0xdf */
  776.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xe0 - 0xef */
  777.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0xf0 - 0xff */
  778. };
  779. static const u_char oneruns[256] = {
  780.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x00 - 0x0f */
  781.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x10 - 0x1f */
  782.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x20 - 0x2f */
  783.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x30 - 0x3f */
  784.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x40 - 0x4f */
  785.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x50 - 0x5f */
  786.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x60 - 0x6f */
  787.     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,    /* 0x70 - 0x7f */
  788.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x80 - 0x8f */
  789.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0x90 - 0x9f */
  790.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0xa0 - 0xaf */
  791.     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,    /* 0xb0 - 0xbf */
  792.     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,    /* 0xc0 - 0xcf */
  793.     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,    /* 0xd0 - 0xdf */
  794.     3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,    /* 0xe0 - 0xef */
  795.     4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 7, 8,    /* 0xf0 - 0xff */
  796. };
  797.  
  798. /*
  799.  * Reset encoding state at the start of a strip.
  800.  */
  801. static
  802. DECLARE1(Fax3PreEncode, TIFF*, tif)
  803. {
  804.     Fax3EncodeState *sp = (Fax3EncodeState *)tif->tif_data;
  805.  
  806.     if (sp == NULL) {
  807.         sp = (Fax3EncodeState *)Fax3SetupState(tif, sizeof (*sp));
  808.         if (!sp)
  809.             return (0);
  810.         if (sp->b.white == 0) {
  811.             sp->wruns = zeroruns;
  812.             sp->bruns = oneruns;
  813.         } else {
  814.             sp->wruns = oneruns;
  815.             sp->bruns = zeroruns;
  816.         }
  817.     }
  818.     sp->b.bit = 8;
  819.     sp->b.data = 0;
  820.     sp->b.tag = G3_1D;
  821.     /*
  822.      * This is necessary for Group 4; otherwise it isn't
  823.      * needed because the first scanline of each strip ends
  824.      * up being copied into the refline.
  825.      */
  826.     if (sp->b.refline)
  827.         bset(sp->b.refline, sp->b.rowbytes, sp->b.white ? 0xff : 0x00);
  828.     if (is2DEncoding(tif)) {
  829.         float res = tif->tif_dir.td_yresolution;
  830.         /*
  831.          * The CCITT spec says that when doing 2d encoding, you
  832.          * should only do it on K consecutive scanlines, where K
  833.          * depends on the resolution of the image being encoded
  834.          * (2 for <= 200 lpi, 4 for > 200 lpi).  Since the directory
  835.          * code initializes td_yresolution to 0, this code will
  836.          * select a K of 2 unless the YResolution tag is set
  837.          * appropriately.  (Note also that we fudge a little here
  838.          * and use 150 lpi to avoid problems with units conversion.)
  839.          */
  840.         if (tif->tif_dir.td_resolutionunit == RESUNIT_CENTIMETER)
  841.             res = (res * .3937) / 2.54;    /* convert to inches */
  842.         sp->maxk = (res > 150 ? 4 : 2);
  843.         sp->k = sp->maxk-1;
  844.     } else
  845.         sp->k = sp->maxk = 0;
  846.     return (1);
  847. }
  848.  
  849. /*
  850.  * 1d-encode a row of pixels.  The encoding is
  851.  * a sequence of all-white or all-black spans
  852.  * of pixels encoded with Huffman codes.
  853.  */
  854. static int
  855. DECLARE3(Fax3Encode1DRow, TIFF*, tif, u_char*, bp, int, bits)
  856. {
  857.     Fax3EncodeState *sp = (Fax3EncodeState *)tif->tif_data;
  858.     int bs = 0, span;
  859.  
  860.     for (;;) {
  861.         span = findspan(&bp, bs, bits, sp->wruns);    /* white span */
  862.         putspan(tif, span, TIFFFaxWhiteCodes);
  863.         bs += span;
  864.         if (bs >= bits)
  865.             break;
  866.         span = findspan(&bp, bs, bits, sp->bruns);    /* black span */
  867.         putspan(tif, span, TIFFFaxBlackCodes);
  868.         bs += span;
  869.         if (bs >= bits)
  870.             break;
  871.     }
  872.     return (1);
  873. }
  874.  
  875. static const tableentry horizcode =
  876.     { 3, 0x1 };        /* 001 */
  877. static const tableentry passcode =
  878.     { 4, 0x1 };        /* 0001 */
  879. static const tableentry vcodes[7] = {
  880.     { 7, 0x03 },    /* 0000 011 */
  881.     { 6, 0x03 },    /* 0000 11 */
  882.     { 3, 0x03 },    /* 011 */
  883.     { 1, 0x1 },        /* 1 */
  884.     { 3, 0x2 },        /* 010 */
  885.     { 6, 0x02 },    /* 0000 10 */
  886.     { 7, 0x02 }        /* 0000 010 */
  887. };
  888.  
  889. /*
  890.  * 2d-encode a row of pixels.  Consult the CCITT
  891.  * documentation for the algorithm.
  892.  */
  893. int
  894. DECLARE4(Fax3Encode2DRow, TIFF*, tif, u_char*, bp, u_char*, rp, int, bits)
  895. {
  896. #define    PIXEL(buf,ix)    ((((buf)[(ix)>>3]) >> (7-((ix)&7))) & 1)
  897.     short white = ((Fax3BaseState *)tif->tif_data)->white;
  898.     int a0 = 0;
  899.     int a1 = (PIXEL(bp, 0) != white ? 0 : finddiff(bp, 0, bits, white));
  900.     int b1 = (PIXEL(rp, 0) != white ? 0 : finddiff(rp, 0, bits, white));
  901.     int a2, b2;
  902.  
  903.     for (;;) {
  904.         b2 = finddiff(rp, b1, bits, PIXEL(rp,b1));
  905.         if (b2 >= a1) {
  906.             int d = b1 - a1;
  907.             if (!(-3 <= d && d <= 3)) {    /* horizontal mode */
  908.                 a2 = finddiff(bp, a1, bits, PIXEL(bp,a1));
  909.                 putcode(tif, &horizcode);
  910.                 if (a0+a1 == 0 || PIXEL(bp, a0) == white) {
  911.                     putspan(tif, a1-a0, TIFFFaxWhiteCodes);
  912.                     putspan(tif, a2-a1, TIFFFaxBlackCodes);
  913.                 } else {
  914.                     putspan(tif, a1-a0, TIFFFaxBlackCodes);
  915.                     putspan(tif, a2-a1, TIFFFaxWhiteCodes);
  916.                 }
  917.                 a0 = a2;
  918.             } else {            /* vertical mode */
  919.                 putcode(tif, &vcodes[d+3]);
  920.                 a0 = a1;
  921.             }
  922.         } else {                /* pass mode */
  923.             putcode(tif, &passcode);
  924.             a0 = b2;
  925.         }
  926.         if (a0 >= bits)
  927.             break;
  928.         a1 = finddiff(bp, a0, bits, PIXEL(bp,a0));
  929.         b1 = finddiff(rp, a0, bits, !PIXEL(bp,a0));
  930.         b1 = finddiff(rp, b1, bits, PIXEL(bp,a0));
  931.     }
  932.     return (1);
  933. #undef PIXEL
  934. }
  935.  
  936. /*
  937.  * Encode a buffer of pixels.
  938.  */
  939. static int
  940. DECLARE4(Fax3Encode, TIFF*, tif, u_char*, bp, u_long, cc, u_int, s)
  941. {
  942.     Fax3EncodeState *sp = (Fax3EncodeState *)tif->tif_data;
  943.  
  944.     while ((long)cc > 0) {
  945.         Fax3PutEOL(tif);
  946.         if (is2DEncoding(tif)) {
  947.             if (sp->b.tag == G3_1D) {
  948.                 if (!Fax3Encode1DRow(tif, bp, sp->b.rowpixels))
  949.                     return (0);
  950.                 sp->b.tag = G3_2D;
  951.             } else {
  952.                 if (!Fax3Encode2DRow(tif, bp, sp->b.refline, sp->b.rowpixels))
  953.                     return (0);
  954.                 sp->k--;
  955.             }
  956.             if (sp->k == 0) {
  957.                 sp->b.tag = G3_1D;
  958.                 sp->k = sp->maxk-1;
  959.             } else
  960.                 memcpy(sp->b.refline, bp, sp->b.rowbytes);
  961.         } else {
  962.             if (!Fax3Encode1DRow(tif, bp, sp->b.rowpixels))
  963.                 return (0);
  964.         }
  965.         bp += sp->b.rowbytes;
  966.         cc -= sp->b.rowbytes;
  967.         if (cc > 0)
  968.             tif->tif_row++;
  969.     }
  970.     return (1);
  971. }
  972.  
  973. static int
  974. DECLARE1(Fax3PostEncode, TIFF*, tif)
  975. {
  976.     Fax3BaseState *sp = (Fax3BaseState *)tif->tif_data;
  977.  
  978.     if (sp->bit != 8)
  979.         Fax3FlushBits(tif, sp);
  980.     return (1);
  981. }
  982.  
  983. static
  984. DECLARE1(Fax3Close, TIFF*, tif)
  985. {
  986.     if ((tif->tif_options & FAX3_CLASSF) == 0) {    /* append RTC */
  987.         int i;
  988.         for (i = 0; i < 6; i++) {
  989.             Fax3PutBits(tif, EOL, 12);
  990.             if (is2DEncoding(tif))
  991.                 Fax3PutBits(tif, 1, 1);
  992.         }
  993.         (void) Fax3PostEncode(tif);
  994.     }
  995. }
  996.  
  997. static
  998. DECLARE1(Fax3Cleanup, TIFF*, tif)
  999. {
  1000.     if (tif->tif_data) {
  1001.         _TIFFfree(tif->tif_data);
  1002.         tif->tif_data = NULL;
  1003.     }
  1004. }
  1005.  
  1006. /*
  1007.  * Bit handling utilities.
  1008.  */
  1009.  
  1010. /*
  1011.  * Find a span of ones or zeros using the supplied
  1012.  * table.  The byte-aligned start of the bit string
  1013.  * is supplied along with the start+end bit indices.
  1014.  * The table gives the number of consecutive ones or
  1015.  * zeros starting from the msb and is indexed by byte
  1016.  * value.
  1017.  */
  1018. static int
  1019. DECLARE4(findspan, u_char**, bpp, int, bs, int, be, register const u_char*, tab)
  1020. {
  1021.     register u_char *bp = *bpp;
  1022.     register int bits = be - bs;
  1023.     register int n, span;
  1024.  
  1025.     /*
  1026.      * Check partial byte on lhs.
  1027.      */
  1028.     if (bits > 0 && (n = (bs & 7))) {
  1029.         span = tab[(*bp << n) & 0xff];
  1030.         if (span > 8-n)        /* table value too generous */
  1031.             span = 8-n;
  1032.         if (span > bits)    /* constrain span to bit range */
  1033.             span = bits;
  1034.         if (n+span < 8)        /* doesn't extend to edge of byte */
  1035.             goto done;
  1036.         bits -= span;
  1037.         bp++;
  1038.     } else
  1039.         span = 0;
  1040.     /*
  1041.      * Scan full bytes for all 1's or all 0's.
  1042.      */
  1043.     while (bits >= 8) {
  1044.         n = tab[*bp];
  1045.         span += n;
  1046.         bits -= n;
  1047.         if (n < 8)        /* end of run */
  1048.             goto done;
  1049.         bp++;
  1050.     }
  1051.     /*
  1052.      * Check partial byte on rhs.
  1053.      */
  1054.     if (bits > 0) {
  1055.         n = tab[*bp];
  1056.         span += (n > bits ? bits : n);
  1057.     }
  1058. done:
  1059.     *bpp = bp;
  1060.     return (span);
  1061. }
  1062.  
  1063. /*
  1064.  * Return the offset of the next bit in the range
  1065.  * [bs..be] that is different from the specified
  1066.  * color.  The end, be, is returned if no such bit
  1067.  * exists.
  1068.  */
  1069. static int
  1070. DECLARE4(finddiff, u_char*, cp, int, bs, int, be, int, color)
  1071. {
  1072.     cp += bs >> 3;            /* adjust byte offset */
  1073.     return (bs + findspan(&cp, bs, be, color ? oneruns : zeroruns));
  1074. }
  1075.  
  1076. int
  1077. DECLARE1(TIFFInitCCITTFax3, TIFF*, tif)
  1078. {
  1079.     tif->tif_predecode = Fax3PreDecode;
  1080.     tif->tif_decoderow = Fax3Decode;
  1081.     tif->tif_decodestrip = Fax3Decode;
  1082.     tif->tif_decodetile = Fax3Decode;
  1083.     tif->tif_preencode = Fax3PreEncode;
  1084.     tif->tif_postencode = Fax3PostEncode;
  1085.     tif->tif_encoderow = Fax3Encode;
  1086.     tif->tif_encodestrip = Fax3Encode;
  1087.     tif->tif_encodetile = Fax3Encode;
  1088.     tif->tif_close = Fax3Close;
  1089.     tif->tif_cleanup = Fax3Cleanup;
  1090.     tif->tif_options |= FAX3_CLASSF;    /* default */
  1091.     tif->tif_flags |= TIFF_NOBITREV;    /* we handle bit reversal */
  1092.     return (1);
  1093. }
  1094.